package com.code.test.first.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.md
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 * <p>
 * 说明：
 * <p>
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
 * <p>
 * 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
 */
public class Code216 {

    public static void main(String[] args) {
        List<List<Integer>> ret = combine(7, 3);
        System.out.println(ret);
    }

    static List<List<Integer>> ret = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();

    public static List<List<Integer>> combine(int targetSum, int k) {
        backtracking(targetSum, 0, k, 1);

        return ret;
    }


    public static void backtracking(int targetSum, int curSum, int k, int startIndex) {
        if (curSum > targetSum) {
            return;
        }
        //每一次采集结果的数量与要求的组合数相等
        if (path.size() == k) {
            //放入条件是等于n
            if (curSum == targetSum) ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            //把自己放进去
            path.add(i);
            //这里加完
            curSum += i;

            //然后从剩下的取一个数，再往下，发现符合组合要求，则放到结果集
            backtracking(targetSum, curSum, k, i + 1);
            //再把自己移除，比如 [1,2]→[1]→ [1,3]→[1]→[1,4]
            path.removeLast();
            //这里也要回溯
            curSum -= i;
        }
    }

}
